Complete Binary Tree যার height n, তার মধ্যে node কতটি?

একটি বাইনারি ট্রির (Binary Tree) উচ্চতা (height) বলতে এর রুট (root) থেকে গভীরতম পাতার (deepest leaf) দূরত্বকে বোঝায়। যদি একটি মাত্র নোড থাকে, তবে তার উচ্চতা 0 ধরা হয়। যদি রুট থেকে গভীরতম পাতার দূরত্ব n সংখ্যক প্রান্ত (edges) দ্বারা গঠিত হয়, তবে সেই ট্রির উচ্চতা n।

একটি কমপ্লিট বাইনারি ট্রি (Complete Binary Tree) হলো এমন একটি বাইনারি ট্রি, যেখানে শেষ স্তর (last level) ব্যতীত বাকি সকল স্তর সম্পূর্ণরূপে ভরা থাকে এবং শেষ স্তরটি বাম দিক থেকে ডানে পূর্ণ করা হয়।

একটি পারফেক্ট বাইনারি ট্রি (Perfect Binary Tree) হলো এমন একটি ট্রি যা ফুল (full) এবং কমপ্লিট (complete) উভয়ই। এর মানে হলো, এই ট্রির সকল অভ্যন্তরীণ নোডের ঠিক দুটি সন্তান থাকে এবং সকল পাতা একই স্তরে অবস্থিত। একটি পারফেক্ট বাইনারি ট্রি একটি কমপ্লিট বাইনারি ট্রির একটি বিশেষ রূপ যেখানে প্রদত্ত উচ্চতার জন্য সর্বাধিক সংখ্যক নোড থাকে। সাধারণত, যখন একটি নির্দিষ্ট ফর্মুলা অপশন হিসেবে থাকে, তখন পারফেক্ট বাইনারি ট্রির নোড সংখ্যাই চাওয়া হয়।

একটি পারফেক্ট বাইনারি ট্রিতে (যা একটি কমপ্লিট বাইনারি ট্রি) উচ্চতা 'n' হলে নোড সংখ্যা নিম্নরূপ:

    
• লেভেল 0 (root): \(2^0 = 1\) নোড
    
• লেভেল 1: \(2^1 = 2\) নোড
    
• লেভেল 2: \(2^2 = 4\) নোড
    
• ...
    
• লেভেল n: \(2^n\) নোড

অতএব, উচ্চতা 'n' এর একটি পারফেক্ট বাইনারি ট্রির মোট নোড সংখ্যা হবে সকল স্তরের নোড সংখ্যার যোগফল:

\( \text{মোট নোড} = 2^0 + 2^1 + 2^2 + \dots + 2^n \)

এটি একটি জ্যামিতিক ধারা (Geometric Progression) যার যোগফল নির্ণয়ের সূত্র হলো \( \frac{a(r^{k+1}-1)}{r-1} \), যেখানে \(a=2^0=1\), \(r=2\) এবং পদের সংখ্যা \(k+1 = n+1\) (0 থেকে n পর্যন্ত)।

সুতরাং, মোট নোড সংখ্যা \( = \frac{1 \cdot (2^{n+1}-1)}{2-1} = 2^{n+1}-1 \)

উদাহরণ:

    
• উচ্চতা n = 0 (শুধুমাত্র রুট নোড): নোড সংখ্যা = \(2^{0+1}-1 = 2^1-1 = 1\)
    
• উচ্চতা n = 1 (রুট এবং দুটি সন্তান): নোড সংখ্যা = \(2^{1+1}-1 = 2^2-1 = 3\)
    
• উচ্চতা n = 2: নোড সংখ্যা = \(2^{2+1}-1 = 2^3-1 = 7\)

এই সূত্রটি একটি পারফেক্ট বাইনারি ট্রির নোড সংখ্যা প্রকাশ করে, যা প্রদত্ত উচ্চতার একটি কমপ্লিট বাইনারি ট্রিতে সর্বোচ্চ সংখ্যক নোড থাকতে পারে।

অতএব, সঠিক উত্তর হলো \(2^{n+1}-1\)।